In an orthogonal frequency division multiplexing system (hereinafter referred to as OFDM), N-point (where N being an integer) discrete Fourier transform (hereinafter referred to as DFT) is required. The number of mathematical operation of the DFT is proportional to N. When N is large, an algorithm capable of performing the DFT operation effectively is required. A fast Fourier transform (hereinafter referred to as FFT) is capable of continuously dividing an N-length input sequence into a plurality of smaller subsequences. That is, the FFT is such an algorithm capable of decreasing the number of the DFT operation significantly. Being served as an algorithm capable of dividing an N-length sequence into a plurality of smaller subsequences, the FFT comprises a decimation-in-time (hereinafter referred to as DIT) algorithm and a decimation-in-frequency (hereinafter referred to as DIF) algorithm. Since the N-point FFT algorithm can be designed in an OFDM modulation/demodulation system, the OFDM modulation/demodulation system is capable of implementing the DIT algorithm and the DIF algorithm.
The FFT is utilized to transform time domain signals into frequency domain signals; the IFFT is utilized to transform the frequency domain signals into the time domain signals. Because there is a need to analyze the frequency domain in wireless communications, it is more effective to perform channel estimation by using the frequency domain signals generated by the FFT. A conventional FFT apparatus comprises a single processing element structure (hereinafter referred to as SPE) utilizing shared memory, and a pipeline structure utilizing delay feedback registers among operators of operating stages.
An N-point FFT apparatus which is implemented by the SPE structure requires the number of operating stages to be the same as the number of N samples memory read/write access. As a result, there is a drawback of great output latency in the SPE structure. In contrast, an advantage in the pipeline structure is that the output latency of the pipeline structure is only N-cycles. Although memory depth of the pipeline structure is the same as the SPE structure, drawbacks of the pipeline structure includes requiring the same number of memory as the operating stages, and orders of input data are different from orders of output data. Accordingly, in order to easily proceed processes after the FFT operation, memories for transforming data sequence are added, and the output latency with regard to a maximum range of the N-cycles is increased, so that the orders of input data are the same as the orders of output data.
Since the FFT apparatus being utilized in the OFDM modulation/demodulation system requires to process a plurality of continuous FFT signals, memories are needed to store a next signal while a current signal is processed. In addition, memories having the delay feedback registers constitute each operating stage of the FFT in the pipeline structure. The memories will occupy a greater part of an area in the FFT apparatus. Accordingly, a greater number of memories will lead to a drawback of occupying a larger area in the system.